/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        322.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 14:15
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 零钱兑换
 * 给定不同面额的硬币 coins 和一个总金额 amount。
 * 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回-1。
 */
#include <vector>
using namespace std;
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i] 表示 金额为i时的硬币数目
        vector<int> dp(amount + 1,amount + 1); // 给dp[i]赋一个不可能达到的初值
        dp[0] = 0;
        for (int i = 0; i < dp.size(); ++i) {
            for(auto &coin: coins){
                if (i - coin < 0)
                    continue;
                dp[i] = min(dp[i],dp[i-coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1:dp[amount];

    }
};